Leetcode Attempted Algorithms

2017-11-02

先做一个简短的总结吧，leetcode的目前的进度是 332/632。平台因为每周都会举行Contest,所以题目仍然一直在增加。以我目前投入的精力和时间，应该是切不完(无奈笑)。不过每次提交也是乐在其中。

这次把自己Attempted(提交过，没有通过的)题目拖出来，重点审视一下。这些题目都是自己的短板。

序号	题目	难度	通过率
132	Palindrome Partitioning II	Hard	24.0%
218	The Skyline Problem	Hard	26.8%
220	Contains Duplicate III	Medium	19.1%
222	Count Complete Tree Nodes	Medium	27.3%
395	Longest Substring with At Least K Repeating Characters	Medium	35.5%
421	Maximum XOR of Two Numbers in an Array	Medium	46.6%
437	Path Sum III	Easy	39.5%
522	Longest Uncommon Subsequence II	Medium	30.4%
673	Number of Longest Increasing Subsequence	Medium	31.1%

Palindrome Partitioning II

题目大意

给定一个字符串s，分割成各个子串使其都为回文串。请问最小分割次数为多少。

解题思路

我一开始使用 广度优化搜索 这种暴力的枚举方式。

思路是枚举每一个index，切分得到两个子串若都为回文串则返回当前步数(广度优化保证为最小答案)。若只有一个子串为回文串，则将另一个子串(非回文串)加入队列接着枚举。若两个都不是，则跳过该index。
跑测试用例是没有问题，答案都是正确的。可惜超时了。

1 2	25 / 29 test cases passed. Status: Time Limit Exceeded

后台给出的用例是这个:"fifgbeajcacehiicccfecbfhhgfiiecdcjjffbghdidbhbdbfbfjccgbbdcjheccfbhafehieabbdfeigbiaggchaeghaijfbjhi"。我在main函数里面加了统计时间方法，是15774.1 ms。

这个思路最大的问题在于，如果目标串(s)过长，没有合理剪枝的情况下会产生很多冗余的状态压入队列导致超时。

进而思考，有没有存在剪枝使得枚举过的状态是单一可查的，避免无用低效的穷举。

Longest Substring with At Least K Repeating Characters Accepted

题目大意

在给定的只有小写字母的字符串中找出最长子串T，使得T中的每个字符至少出现过k次

解题思路

枚举T字符串的起始位置(index)和长度(length）。构造出字符串之后，开始统计字符出现次数并对比k。

做法上几乎纯模拟，最后超时。用例就不贴了，T巨长。

1 2	27 / 28 test cases passed. Status: Time Limit Exceeded

最后，借鉴了别人的思路，采用二分法缩小范围。具体看实现代码：

class Solution {
public:
   int longestSubstring(string s, int k) {
       if(k == 0) return (int)s.size();
       if(s.size() == 0 || s.size() < k) return 0;
       int table[26] = {0};
       for (char c : s){
           ++table[c - 'a'];
       }
       size_t idx = 0;
       while(idx < s.size() && table[s[idx] - 'a'] >= k) ++idx;
       if(idx == s.size()) return (int)s.size();
       int left = longestSubstring(s.substr(0,idx), k);
       int right = longestSubstring(s.substr(idx+1), k);
       return max(left, right);
   }
};

The Skyline Problem

题目大意

给出一组建筑的数据(Li,Ri,Hi)。Li和Ri表示该ith建筑物的左边x轴值和右边x轴值，Hi表示建筑物高度。三个数据可在二维坐标系第一象限中明确出建筑物的矩形区域。

求打印出”天际线”：这些线上的点在建筑群投影面积的水平线段左侧，通过”天际线”可以描绘出建筑群的投影面积。

解题思路

看题目意识到是一道动态区间求最大值的问题，动态在于区间中的高度最大值是会更新的(建筑彼此之间可以重叠覆盖)。

知道了各个重叠区间的最高值，最后才能知道sky line的key points所在。

按照线段树的做法，提交了一次。结果超内存了，Memory Limit Exceeded。

我的线段树，区间节点划分太细了，叶子节点是一个整数。而测试集的范围是[0,10000]。爆内存太正常了，后续的优化方向应该是将叶子节点优化为区间。